前端界面库展示

Appearance

ADT ​

Alt text

  • There are three Abstract Data Types(ADT) that we normally use in the program:
    • stack
    • queue
    • linked list

Alt text

Stack ​

  • In programming terms, putting an item on top of the stack is called push and removing an item is called pop.
  • Item 3 was kept last, it was removed first. This is exactly how the LIFO (Last In First Out) Principle works.

Alt text

  • A stack can be implemented using an array and a set of pointers.
  • As an array has a finite size, the stack may become full and this condition must be allowed for.

Alt text

To set up a stack ​

DECLARE stack ARRAY[1:10] OF INTEGER
DECLARE topPointer : INTEGER
DECLARE basePointer : INTEGER
DECLARE stackful : INTEGER
basePointer ← 1
topPointer ← 0
stackful ← 10

To push an item, stored in item, onto a stack ​

IF topPointer < stackful THEN
  topPointer ← topPointer + 1
  stack[topPointer] ← item
ELSE
  OUTPUT "Stack is full, cannot push"
ENDIF

To pop an item, stored in item, from the stack ​

IF topPointer = basePointer - 1 THEN
  OUTPUT "Stack is empty, cannot pop"
ELSE
  Item ← stack[topPointer]
  topPointer ← topPointer - 1
ENDIF

Queue ​

  • A queue is a useful data structure in programming.
  • It is similar to the ticket queue outside a cinema hall, where the first person entering the queue is the first person who gets the ticket.
  • Queue follows the First In First Out (FIFO) rule - the item that goes in first is the item that comes out first.

Alt text

  • A queue can be implemented using an array and a set of pointers.
  • As an array has a finite size, the queue may become full and this condition must be allowed for.

Alt text

Alt text

To set up a queue ​

DECLARE queue ARRAY[1:10] OF INTEGER
DECLARE rearPointer : INTEGER
DECLARE frontPointer : INTEGER
DECLARE queueful : INTEGER
DECLARE queueLength : INTEGER
frontPointer ← 1
endPointer ← 0
upperBound ← 10
queueful ← 10
queueLength ← 0

To add an item, stored in item, onto a queue ​

IF queueLength < queueful THEN
  IF rearPointer < upperBound THEN
    rearPointer ← rearPointer + 1
  ELSE
    rearPointer ← 1
  ENDIF
  queueLength ← queueLength + 1
  queue[rearPointer] ← item
ELSE
  OUTPUT "Queue is full, cannot enqueue"
ENDIF

To remove an item from the queue and store in item ​

IF queueLength = 0 THEN
  OUTPUT "Queue is empty, cannot dequeue"
ELSE
  Item ← queue[frontPointer]
  IF frontPointer = upperBound THEN
    frontPointer ← 1
  ELSE
    frontPointer ← frontPointer + 1
  ENDIF
  queueLength ← queueLength - 1
ENDIF

Linked list ​

  • A linked list is a linear data structure that includes a series of connected nodes.
  • Here, each node stores the data and the address of the next node.

Alt text

  • A linked list can be implemented using two 1D arrays, one for the items in the linked list and another for the pointers to the next item in the list, and a set of pointers.

Alt text

To set up a linked list ​

DECLARE mylinkedList ARRAY[0:11] OF INTEGER
DECLARE myLinkedListPointers ARRAY[0:11] OF INTEGER
DECLARE startPointer : INTEGER
DECLARE heapStartPointer : INTEGER
DECLARE index : INTEGER
heapStartPointer ← 0
startPointer ← –1 // list empty
FOR index ← 0 TO 11
  myLinkedListPointers[index] ← index + 1
NEXT index
// the linked list heap is a linked list of all the spaces in the linked list, this is set up when the linked list is initialised
myLinkedListPointers[11] ← –1
// the final heap pointer is set to –1 to show no further links
IdentifierDescription
myLinkedListLinked list to be searched
myLinkedListPointersPointers for linked list
startPointerStart of the linked list
heapStartPointerStart of the heap
indexPointer to current element in the linked list

ADT

Which one follows the (First In First Out (FIFO) rule?

[0/1]